
public class fibonacci {

    public static void main(String[] args) {
        
        System.out.println("hello world");
        fibonacci f = new fibonacci();
        for(int i = 0; i < 9; i++)
            System.out.println("alg 1 -- i = " + i + "; result is " + f.alg1(i));
        for(int i = 0; i < 9; i++)
            System.out.println("alg 2 -- i = " + i + "; result is " + f.alg2(i));
        for(int i = 0; i < 9; i++) {
            int[] memo = new int[i+1];
            System.out.println("alg 3 -- i = " + i + "; result is " + f.alg3(i, memo));
        }
    }

    int alg1(int n)
    {
        if (n <= 1)
            return n;
        else 
            return alg1(n-1) + alg1(n-2);
    }

    int alg2(int n)
    {
        if (n <= 1) 
            return n;
        int[] a = {0,1,1};
        
        for(int i = 2; i <= n; i++) {
            a[2] = a[1] + a[0];
            a[0] = a[1];
            a[1] = a[2]; 
        }
        return a[2];
    }

    int alg3(int n, int[] memo) {
        if ( n <= 1)
            return n;
        
        if (memo[n] == 0) {
            memo[n] = alg3(n-1, memo) + alg3(n-2, memo);
        } 
        return memo[n];
    }
}